package com.future;

import com.future.util.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * Description: 865. 具有所有最深节点的最小子树
 * 关键词： 所有 最深节点
 * 也就是说：如果一棵树中，有n个节点最大深度一样，那么返回包含所有最深节点的最小子树！！！
 *
 * @author weiruibai.vendor
 * Date: 2023/1/9 14:50
 */
public class Solution_865 {

    private static Solution_865 instance = new Solution_865();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        TreeNode p = new TreeNode(0);
        p.left = new TreeNode(-100);

        root.left.left = p;
        root.left.right = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        root.left.right.left = node3;

        /*node3.left = new TreeNode(100);
        node3.left.left = new TreeNode(-90);*/
        root.left.right.right = new TreeNode(5);


        root.right = new TreeNode(8);
        TreeNode q = new TreeNode(7);
        root.right.left = q;
        root.right.right = new TreeNode(9);

        // [0,1,null,3,2,6,null,5,4]
        // 预期 [1,3,2,6,null,5,4]
        System.out.println(instance.subtreeWithAllDeepest(root));

    }

    /**
     * @param root
     * @return
     */
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        LinkedList linked = new LinkedList();
        LinkedList<Msg> optionAns = new LinkedList<>();
        /**
         * 获取所有叶子节点信息以及从跟节点到叶子节点的路径和高度
         */
        getLeavesMsg(root, linked, optionAns, 0);
        /**
         * 倒序排序
         */
        optionAns.sort((o1, o2) -> o2.height - o1.height);
        int maxHeight = optionAns.get(0).height;
        /**
         * 只留最大深度的
         */
        while (maxHeight != optionAns.peekLast().height) {
            optionAns.pollLast();
        }
        int n = optionAns.size();
        TreeNode ans = optionAns.get(0).node;
        int maxNodeSum = Integer.MIN_VALUE;
        /**
         * 在最大深度的节点基础上，求包含所有最大深度节点的最小子树
         */
        for (int i = 0; i < n - 1; i++) {
            Msg node1 = optionAns.get(i);
            for (int j = i + 1; j < n; j++) {
                Msg node2 = optionAns.get(j);
                Info info = lowestCommonAncestor(new LinkedList<>(node1.stack), new LinkedList<>(node2.stack));
                if (info.nodeNum > maxNodeSum) {
                    maxNodeSum = info.nodeNum;
                    ans = info.parentNode;
                }
            }
        }
        return ans;
    }

    /**
     * 获取最小公共祖先
     *
     * @param stack
     * @param stack1
     * @return
     */
    private Info lowestCommonAncestor(LinkedList<TreeNode> stack, LinkedList<TreeNode> stack1) {
        int nodeNums = stack.size() + stack1.size();
        TreeNode ans = stack1.pollFirst();
        TreeNode curNode = ans;
        while (stack.contains(curNode)) {
            nodeNums -= 2;
            ans = curNode;
            curNode = stack1.pollFirst();
        }
        return new Info(nodeNums, ans);
    }

    /**
     * 返回叶子节点到跟节点的高度、叶子节点和根到叶子节点的路径
     *
     * @param root
     * @param list
     * @param optionAns
     * @param height
     */
    private void getLeavesMsg(TreeNode root, LinkedList<TreeNode> list, List<Msg> optionAns, int height) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) { // 叶子
            LinkedList<TreeNode> copy = new LinkedList<>(list);
            copy.add(root);
            Msg msg = new Msg(copy, root, height);
            optionAns.add(msg);
            return;
        }
        height++;
        list.addLast(root);
        getLeavesMsg(root.left, list, optionAns, height);
        getLeavesMsg(root.right, list, optionAns, height);
        list.removeLast();
    }


    private class Info {

        private int nodeNum;

        private TreeNode parentNode;

        public Info(int nodeNum, TreeNode parentNode) {
            this.nodeNum = nodeNum;
            this.parentNode = parentNode;
        }
    }

    private class Msg {
        private LinkedList<TreeNode> stack;
        private TreeNode node;
        private Integer height;

        public Msg(LinkedList<TreeNode> stack, TreeNode node, Integer height) {
            this.stack = stack;
            this.node = node;
            this.height = height;
        }

        @Override
        public String toString() {
            return "Msg{" +
                    "node=" + node +
                    ", height=" + height +
                    '}';
        }
    }
}
